# -*- coding: utf-8 -*-
"""
作者: liuzaiqiang
邮箱: zaiqiangliu@163.com
地址: 新疆大学
创建时间: 2025/11/14 22:01
功能描述:

题目背景：
    在处理实验数据或日志文件时，数据通常是按时间戳排序的。一个常见的需求是：快速找到某个特定时间点之后的第一条记录。例如，在一天的气温记录中，找到气温首次超过30度的那个时刻。如果数据量巨大，线性扫描会非常耗时，而二分查找则是一个高效得多的选择。

题目描述：
    给定一个按时间戳升序排列的日志列表 logs ，每个日志是一个元组 (timestamp, event_data) 。
    请编写一个函数 find_first_occurrence ，该函数接收 logs 列表和一个目标时间戳target_timestamp ，并返回列表中第一个时间戳大于或等于 target_timestamp 的日志。如果不存在这样的日志，则返回 None 。

要求：
    1. 必须使用二分查找算法来保证效率。
    2. 使用函数式编程，例如将数据提取和比较的逻辑用 lambda 函数来表达，使代码更具通用
    性。

"""
from typing import List, Tuple, Any, Optional, Callable


def find_first_occurrence(sorted_list: List[Any],
                          target: Any,
                          key: Callable[[Any],Any] = lambda x: x)-> Optional[Any]:
    """
    在已排序的列表中查找目标元素的第一个出现位置(大于或者等于)，支持通过自定义key函数提取排序依据，返回找到的元素（若存在）或 None（若不存在）。

    :argument
        参数1：sorted_list: List[Any]: 已经排好序的列表（传过来之前会排好序，本方法内部无需再排序） 注：Any 表示列表元素可以是任何类型（整数、字符串、对象等）。
        参数2：target: Any  要查找的目标值，类型为 Any（与第一个参数的列表元素类型兼容）。
        参数3：key: Callable[[Any], Any] = lambda x: x    可选参数(因为后面有等号，显示定义了默认值)，类型为 “可调用对象”（通常是函数），用于从列表元素中提取用于比较的 “关键字”。
                                                        默认值 lambda x: x 表示 “直接使用元素本身作为关键字”（即按元素自身的值比较）。
                                                        若列表元素是复杂结构（如元组、对象），可通过 key 函数指定排序依据（例如 key=lambda x: x[1] 表示按元素的第二个值比较）
    :returns
        Optional[Any]  表示函数返回值可以是任意类型的元素（找到目标时）或None（未找到目标时）。
                        找到时：返回sorted_list中第一个与 target 匹配的元素（基于 key 函数提取的关键字）。
                        未找到时：返回 None。
    """
    low, high = 0, len(sorted_list) - 1
    result_index = -1
    # 这是一个二分查找的变体，目标是找到满足条件的“最左”边界。
    while low <= high:
        #这种写法比 (low + high) // 2 更安全，可避免整数溢出
        mid = low + (high - low) // 2
        #注意 这里的key方法 是他妈的方法传进来的 不是其他的
        #方法定义处那里 明确将 key 定义为函数的第三个参数，类型是 Callable[[Any], Any]（可调用对象），并且设置了默认值 lambda x: x（即默认直接使用元素本身作为比较关键字）。
        mid_val = key(sorted_list[mid])
        #mid_val = sorted_list[mid]
        if mid_val >= target:
            result_index = mid
            high = mid - 1
        else:
            low = mid + 1
    if result_index != -1:
        return sorted_list[result_index]
    return None

"""
这是一个寻找左边界的二分查找变体，专门用于在有序列表中找到第一个大于等于目标值的元素，保证了结果的唯一性和正确性。通过 key 函数的设计，使该逻辑可适用于各种复杂数据类型（如元组、对象等）的查找场景。
"""
#生成一个变量a,其值为列表[1,2,3,4,5,6,7,8,9,10]中所有元素大于等于5的元素


# 测试代码
if __name__ == '__main__':
    #本题所用来比较的日志文件
    logs = [ (1200, "System Start"),
             (1260, "User Login: Alice"),
             (1320, "CPU Load: 0.8"),
             (1380, "CPU Load: 0.9"),
             (1440, "User Logout: Alice"),
             (1500, "DB Backup Start"),
             (1560, "DB Backup End")
           ]
    # 测试用例 分别要找的目标值 多个 挨个去查找 作为测试
    test_targets = [
        1200,
        1201,
        1260,
        1320,
        1350,
        1560,
        1100,
        1600,
        1440,
        1441
    ]
    for target in test_targets:
        found_log = find_first_occurrence(logs, target, key=lambda log: log[0])
        print(f"{found_log}")





"""
补充1： from typing import List, Tuple, Any, Optional, Callable
在 Python 中，from typing import List, Tuple, Any, Optional, Callable 这行代码用于从 typing 模块导入常用的类型提示工具，这些工具主要用于为代码添加类型注解，提高代码的可读性和可维护性，同时帮助静态类型检查工具（如 mypy）检测潜在的类型错误。以下是对每个导入对象的详细解释：
1. List
作用：
表示一个列表类型，用于注解元素类型统一的列表。
用法：
需要指定列表中元素的类型，格式为 List[元素类型]。
示例：
from typing import List
def process_numbers(numbers: List[int]) -> List[float]:
    return [n / 2 for n in numbers]
上述代码表示 process_numbers 函数接收一个整数列表作为参数，并返回一个浮点数列表。

2. Tuple
作用：
表示一个元组类型，元组是不可变序列，支持固定长度和固定元素类型的注解。
用法：
若元组中元素类型固定且长度固定：Tuple[类型1, 类型2, ...]（如 Tuple[int, str] 表示包含一个整数和一个字符串的二元组）。
若元组中元素类型统一且长度不固定：Tuple[元素类型, ...]（如 Tuple[int, ...] 表示包含任意个整数的元组）。
示例：
from typing import Tuple
def get_person() -> Tuple[str, int]:
    return ("Alice", 30)  # 字符串（姓名）和整数（年龄）的二元组
    
3. Any
作用：
表示任意类型，当变量的类型不确定或不需要限制时使用。
特点：使用 Any 注解的变量可以赋值为任何类型，也可以被任何类型的变量接收，静态检查工具不会对其进行类型校验。
示例：
from typing import Any
def handle_data(data: Any) -> Any:
    # data 可以是任何类型，返回值也可以是任何类型
    return data * 2

4. Optional
作用：
表示一个类型要么是指定的类型，要么是 None。等价于 Union[类型, None]（Union 用于表示 “或” 关系的类型）。
用法：
Optional[类型]，即 类型 | None（Python 3.10+ 可直接用 | 语法替代）。
示例：
from typing import Optional
def find_user(user_id: int) -> Optional[str]:
    if user_id == 1:
        return "Alice"
    else:
        return None  # 可能返回字符串或 None

5. Callable
作用：表示一个可调用对象（如函数、方法、lambda 表达式等），用于注解函数参数或返回值为 “函数” 的场景。
用法：
简单形式：Callable[[参数类型1, 参数类型2, ...],      返回值类型]，
其中 [] 内的第一个元组表示参数类型列表，第二个元素表示返回值类型。
若不关心参数细节，可用 Callable[..., 返回值类型] 表示任意参数的可调用对象。
示例：
from typing import Callable
def apply_func(func: Callable[[int, int], int], a: int, b: int) -> int:
    return func(a, b)  # func 是一个接收两个 int、返回 int 的函数
# 测试：传入加法函数
print(apply_func(lambda x, y: x + y, 2, 3))  # 输出 5


总结
这些类型提示工具的核心作用是增强代码的 “自文档性”，让开发者能更清晰地了解变量、函数参数和返回值的类型。
在实际开发中，结合静态类型检查工具（如 mypy）可以提前发现类型错误，尤其在大型项目中能显著提升代码质量。
注意：Python 3.9+ 引入了 “标准库泛型”（如 list[int] 替代 List[int]，tuple[int, str] 替代 Tuple[int, str]），
但 typing 模块中的这些类型（如 List、Tuple）仍可兼容使用，而 Any、Optional、Callable 等目前仍是常用的类型注解工具。


补充2：
mid = low + (high - low) // 2 可以避免整数溢出 为什么？

当 low 和 high 都是很大的整数时，两者直接相加的结果可能超过当前整数类型能表示的最大值（即溢出），导致计算结果错误。
而 low + (high - low) // 2 可以避免溢出，核心原因是：它先通过 high - low 计算两者的差值（这个差值一定小于 high 和 low 中较大的那个，因此不会溢出），
再将差值除以 2 后与 low 相加。整个过程中没有两个大整数直接相加的操作，因此不会超出整数类型的表示范围，从而避免了溢出。
举例来说：假设整数的最大值为 100，low = 60，high = 70。
(low + high) // 2 = 130 // 2 = 65  60+70这一步就已经溢出了(超过了100)
low + (high - low) // 2 = 60 + (10) // 2 = 65，计算过程中最大的数是 10（差值），不会溢出。
这种写法在二分查找等场景中非常常见，尤其在处理大整数时能保证计算的安全性。



补充3：  mid_val = key(sorted_list[mid]) 
为什么不能直接写：mid_val = sorted_list[mid] 都是可以取到当时的中间值的

让二分查找的核心逻辑（比较、定位）与列表元素的具体结构（比如是元组、字典还是对象）分离开来，彼此不依赖。
key 函数正是通过 “中间转换” 实现了这种分离。
举个例子

场景 1：没有 key 函数（耦合状态）
假设学生信息是元组 (name, score)，如果不使用 key 函数，代码可能会直接写死提取成绩的逻辑：
#直接依赖元素结构（元组的第二个元素）
mid_score = students[mid][1]  # 硬编码了“元组索引1是成绩”
这会导致： 
如果学生信息改成字典 {"name": "张三", "score": 95}，必须修改这行代码为 mid_score = students[mid]["score"]。
如果改成类对象 Student(name="张三", score=95)，又得改成 mid_score = students[mid].score。
核心逻辑与元素结构强耦合，改结构就必须改逻辑，非常不灵活。

场景 2：有 key 函数（解耦状态）
当使用 key 函数时：
#不依赖元素结构，通过key函数转换
mid_score = key(students[mid])
此时：
如果元素是元组 (name, score)，传入 key=lambda x: x[1] 即可。
如果元素是字典 {"name":..., "score":...}，只需传入 key=lambda x: x["score"]。
如果元素是类对象，传入 key=lambda x: x.score 即可。

二分查找的核心逻辑（循环、比较、调整高低指针）完全不用改，只需要修改 key 函数的定义。

总结：key 函数的解耦作用
它相当于在 “元素结构” 和 “二分查找逻辑” 之间加了一层 “翻译器”：
    元素结构变化时，只需要更新 “翻译器”（key 函数）。
    二分查找的核心逻辑（比较、定位）完全不用关心元素是元组、字典还是对象，只管基于 key 函数返回的 “比较值”（比如成绩）进行操作。
这种分离就是 “解耦”，让代码更灵活、更容易维护。


        
"""